package com.markus.code.top100;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/19 22:28
 * todo: 买卖股票的最佳时机
 */
public class LeetCode_121 {
//    public int maxProfit(int[] prices) {
//        if (prices == null || prices.length == 0){
//            return 0;
//        }
////        int [][]profit = new int[prices.length][prices.length];
//        int maxProfit = 0;
//        for (int i=0;i<prices.length-1;i++){
//            for (int j=i+1;j<prices.length;j++){
//                if (prices[i] < prices[j]){
//                    maxProfit = Math.max(prices[j]-prices[i],maxProfit);
//                }
//            }
//        }
//        return maxProfit;
//    }
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0){
            return 0;
        }
        int minPrices = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i=0;i<prices.length;i++){
            if (minPrices > prices[i]){
                minPrices = prices[i];
            }else{
                maxProfit = maxProfit<prices[i]-minPrices?prices[i]-minPrices:maxProfit;
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int []prices = {7,1,5,3,6,4};
        LeetCode_121 demo = new LeetCode_121();
        System.out.println(demo.maxProfit(prices));
    }
}
